package com.mlick.a.leetcode;

public class A1605 {
/*
    方法一：贪心
            思路与算法

    给你两个长度为 nn 和 mm 的非负整数数组 \textit{rowSum}rowSum 和 \textit{colSum}colSum ，其中 \textit{rowSum}[i]rowSum[i] 是二维矩阵中第 ii 行元素的和，\textit{colSum}[j]colSum[j] 是第 jj 列元素的和。现在我们需要返回任意一个大小为 n \times mn×m 并且满足 \textit{rowSum}rowSum 和 \textit{colSum}colSum 要求的二维非负整数矩阵 \textit{matrix}matrix。

    对于 \textit{matrix}matrix 的每一个位置 \textit{matrix}[i][j]matrix[i][j]，0 \le i < n0≤i<n 且 0 \le j < m0≤j<m，我们将 \textit{matrix}[i][j]matrix[i][j] 设为 \min\{\textit{rowSum}[i], \textit{colSum}[j]\}min{rowSum[i],colSum[j]}，然后将 \textit{rowSum}[i], \textit{colSum}[j]rowSum[i],colSum[j] 同时减去 \textit{matrix}[i][j]matrix[i][j] 即可。当遍历完全部位置后，\textit{matrix}matrix 即为一个满足要求的答案矩阵。

    上述的构造方法的正确性说明如下：

    首先我们可以容易得到对于某一个位置 \textit{matrix}[i][j]matrix[i][j] 处理完后，\textit{rowSum}[i]rowSum[i]，\textit{colSum}[j]colSum[j] 一定不会小于 00。然后我们从第一行开始往最后一行构造，因为初始时 \sum_{i = 0}^n \textit{rowSum}[i] = \sum_{j = 0}^m \textit{colSum}[j]∑
    i=0
    n
​
    rowSum[i]=∑
    j=0
    m
​
    colSum[j]，所以对于第一行显然有 \textit{rowSum}[0] \le \sum_{j = 0}^{m} \textit{colSum}[j]rowSum[0]≤∑
    j=0
    m
​
    colSum[j]，所以通过上述操作一定可以使得 \textit{rowSum}[0] = 0rowSum[0]=0，同时满足 \textit{colSum}[j] \ge 0colSum[j]≥0 对于 0 \le j < m0≤j<m 恒成立。然后我们对剩下的 n - 1n−1 行和 mm 列做同样的处理。当处理完成后，\textit{matrix}matrix 为一个符合要求的答案矩阵。

    在实现的过程中，当遍历过程中 \textit{rowSum}[i] = 0rowSum[i]=0，0 \le i < n0≤i<n 时，因为每一个元素为非负整数，所以该行中剩下的元素只能全部为 00，同理对于 \textit{colSum}[j] = 0colSum[j]=0，0 \le j < m0≤j<m 时，该列中剩下的元素也只能全部为 00。所以我们可以初始化 \textit{matrix}matrix 为全零矩阵，在遍历的过程中一旦存在上述情况，则可以直接跳过该行或者列。

*/

    /**
     * 官方 贪心算法，我自己没有想出来
     */
    class Solution {
        public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
            int n = rowSum.length, m = colSum.length;
            int[][] matrix = new int[n][m];
            int i = 0, j = 0;
            while (i < n && j < m) {
                int v = Math.min(rowSum[i], colSum[j]);
                matrix[i][j] = v;
                rowSum[i] -= v;
                colSum[j] -= v;
                if (rowSum[i] == 0) {
                    ++i;
                }
                if (colSum[j] == 0) {
                    ++j;
                }
            }
            return matrix;
        }
    }
}
